Recently, there has been growing interest in developing toll-quality speech coders at rates of 4 kbps and below. The speech quality produced by waveform coders such as code-excited linear prediction (CELP) coders degrades rapidly at rates below 5 kbps [B. S. Atal, and M. R. Schroder, “Stochastic Coding of Speech at Very Low Bit Rate”, Proc. Int. Conf. Comm, Amsterdam, pp. 1610-1613, 1984]. On the other hand, parametric coders such as the waveform-interpolative (WI) coder, the sinusoidal-transform coder (STC), and the multiband-excitation (MBE) coder produce good quality at low rates, but they do not achieve toll quality [Y. Shoham, “High Quality Speech Coding at 2.4 and 4.0 kbps Based on Time Frequency-Interpolation”, IEEE ICASSP'93, Vol. II, pp. 167-170, 1993; W. B. Kleijn, and J. Haagen, “Waveform Interpolation for Coding and Synthesis”, in Speech Coding Synthesis by W. B. Kleijn and K. K. Paliwal, Elsevier Science B. V., Chapter 5, pp. 175-207, 1995; I. S. Burnett, and D. H. Pham, “Multi-Prototye Waveform Coding using Frame-by-Frame Analysis-by-Synthesis”, IEEE ICASSP'97, pp. 1567-1570, 1997; R. J. McAulay, and T. F. Quatieri, “Sinusoidal Coding”, in Speech Coding Synthesis by W. B. Kleijn and K. K. Paliwal, Elsevier Science B. V., Chapter 4, pp. 121-173, 1995; and D. Griffin, and J. S. Lim, “Multiband Excitation Vocoder”, IEEE Trans. ASSP, Vol. 36, No. 8, pp. 1223-1235, August 1988]. This is mainly due to lack of robustness to parameter estimation, which is commonly done in open loop, and to inadequate modeling of non-stationary speech segments. Also, in parametric coders the phase information is commonly not transmitted, and this is for two reasons: first, the phase is of secondary perceptual significance; and second, no efficient phase quantization scheme is known. WI coders typically use a fixed phase vector for the slowly evolving waveform [Shoham, supra; Kleijn et al, supra; and Burnett et al, supra]. For example, in Kleijn et al, a fixed male speaker extracted phase was used. On the other hand, waveform coders such as CELP, by directly quantizing the waveform, implicitly allocate an excessive number of bits to the phase information—more than is perceptually required.